package LeetCode;

public class LC_287_FindtheDuplicateNumber {

    public static void main(String[] args) {

    }

    class Solution {
        public int findDuplicate(int[] nums) {
            int low = 1, high = nums.length - 1;
            int mid = 0;
            while (low < high) {
                mid = low + (high - low) / 2;
                int c = count(nums, mid);

                if (c <= mid) {
                    low = mid + 1;
                } else
                    high = mid;
            }
            return low;
        }

        private int count(int[] nums, int mid) {
            int c = 0;
            for (int num : nums)
                if (num <= mid) c++;
            return c;
        }

    }
}